Матч
322, Расстановка кораблей (BattleshipChecker)
Дивизион 2,
Уровень 3
Рассмотрим игру в морской бой на
поле 10*10. Начальное расположение должно иметь 1 четырехпалубный, 2
трехпалубных, 3 двухпалубных и 4 однопалубных корабля. Корабли должны
располагаться параллельно сторонам игрового поля и не должны касаться друг
друга.
Эффективностью расположения
кораблей называется сумма количества строк и колонок, в которых нет ни одной
ячейки корабля. По заданному расположению кораблей в массиве board вывести “REJECTED”,
если оно не является допустимым. Иначе вывести эффективность их расположения.
Класс: BattleshipChecker
Метод: string checkBoard(vector<string> board)
Ограничения:
board и каждый его элемент
содержит 10 элементов, board[i][j] равно ‘.’
или ‘X’.
Вход. Массив board, содержащий начальное расположение кораблей.
Выход. Вывести “REJECTED”, если board содержит недопустимую расстановку кораблей.
Иначе вывести сообщение “ACCEPTED, X POINTS”,
где X равно эффективности расстановки
кораблей.
Пример входа
|
board |
|
{"......X...", ".XXX..X...", "......X...", "X.X...X...", "X.........", "...XX.X...", "......X...", ".XX...X...", "..........", ".X.X..X..."} |
|
{"X.X.X.X...", "......X...", ".XX...X...", "......X...", "......X..X", "...X..X...", "...X..X...", "......X...", "..XX..X...", "......X..."} |
|
{"X.......X.", "...XXXX...", ".X......X.", "....XX....", ".........X", ".........X", ".....XXX..", ".........X", "..X......X", "..X......X"} |
Пример выхода
“ACCEPTED, 5 POINTS”
“REJECTED”
“ACCEPTED, 0 POINTS”
РЕШЕНИЕ
стратегия + поиск в
глубину
Условие
того, что корабли не касаются друг друга, эквивалентно тому, что не существует
диагональных касаний. То есть ни для каких i,
j (1 £ i, j £ 9) не должно выполняться board[i][j]
= ‘X’ и board[i+1][j+1] = ‘X’ или board[i+1][j]
= ‘X’ и board[i][j+1] = ‘X’.
Если не существует диагональных
касаний, то все корабли имеют вертикальный или горизонтальный вид. При помощи
функции поиска в глубину dfs вычисляем количество кораблей размера 1, 2, 3 и 4.
Если существует корабль размера, большего 4, или существует иное количество
кораблей, чем требуется в условии начального расположения, то выводим “REJECTED”.
Далее находим количество
вертикалей и горизонталей, свободных от кораблей и выводим фразу “ACCEPTED” с соответствующим значением
эффективности расстановки.
ПРОГРАММА
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
int m[5] = {0,4,3,2,1};
vector<string> bd;
int dfs(int i,int j)
{
if ((i < 0) || (i > 9) || (j < 0) || (j >
9)) return 0;
if (bd[i][j] == '.')
return 0;
bd[i][j] = '.';
return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) +
dfs(i,j+1);
}
class BattleshipChecker
{
public:
string checkBoard(vector<string> board)
{
string res="REJECTED";
int i, j, c, row[10], col[10];
char r[20];
bd = board;
for(i = 0; i < 9; i++) for(j = 0; j < 9; j++)
if (((board[i][j] == 'X') && (board[i+1][j+1] == 'X')) ||
((board[i+1][j] == 'X') && (board[i][j+1] == 'X'))) return res;
memset(row,0,sizeof(row));memset(col,0,sizeof(col));
for(i = 0; i < 10; i++) for(j = 0; j < 10; j++)
if (board[i][j] == 'X') row[i] = col[j] = 1;
for(i = 0; i < 10; i++) for(j = 0; j < 10; j++)
if (bd[i][j] == 'X')
{
c = dfs(i,j); if (c > 4) return res;
m[c]--;
}
if (m[1] || m[2] || m[3] || m[4]) return res;
for(c = 20 ,i = 0; i < 10; i++) c -=
row[i] + col[i];
sprintf(r,"ACCEPTED, %d POINTS",c);
res = (string)r;
return res;
}
};